package Review;
//不同的路径III(dfs)
class Solution {

    //定义访问标志
    boolean[][] isVisit;
    //定义数组的全局变量以及路数
    int m,n,step;
    //定义返回值
    int ret;
    //定义遍历数组
    int[] dx = {-1,1,0,0};
    int[] dy = {0,0,-1,1};
    public int uniquePathsIII(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        isVisit = new boolean[m][n];
        //记录起点和终点的坐标
        int bx = 0,by = 0;
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(grid[i][j] == 0) step++;
                else if(grid[i][j] == 1){
                    bx = i;
                    by = j;
                }
            }
        } 
        //因为要加上起点和终点
        //step是统计数组中路径的步数
        step +=2;
        isVisit[bx][by] = true;
        dfs(grid,bx,by,1);
        return ret;
    }
    void dfs(int[][] grid,int i,int j,int count){
        if(grid[i][j] == 2){
            if(count == step){
                ret++;
            }
            //下面的return可有可无 , 系统帮我们结束
            //加上return可以稍微提高一些时间复杂度
            // return;
        }
        for(int k = 0;k<4;k++){
            int x = i+dx[k],y = j+dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !isVisit[x][y] && grid[x][y] != -1){
                isVisit[x][y] = true;
                dfs(grid,x,y,count+1);
                isVisit[x][y] = false;
            }
        }
    }
}